package array;

/**
 * 在一个每一行，每一列都是递增的二维数组中找是否存在一个数字
 */
public class FindInTwoArray {

  /**
   * 遍历查询有没有，时间复杂度o（n2），蛮力
   */
  public void findNum(int[][] array, int num) {

    if (array == null || array.length <= 0) {
      System.out.println("数组为null或者数字没有行列");
      return;
    }

    boolean flag = false;
    label1:
    for (int i = 0; i < array.length; i++) {
      for (int j = 0; j < array[i].length; j++) {
        if (array[i][j] == num) {
          flag = true;
          break label1;
        }
      }
    }
    if (flag) {
      System.out.println("找到了数字" + num);
    } else {
      System.out.println("未找到数字" + num);
    }
  }

  /**
   * 二维数组是有序的，从右上角的开始判断，慢慢缩小范围，时间复杂度就低了，剔除行列的方法
   */
  public void findNum2(int[][] array, int num) {

    boolean flag = false;
    if (array == null || array.length <= 0) {
      System.out.println("数组为null或者数字没有行列");
      return;
    }

    //定义行列 大于这个数字，不会在这一行，小于这个数字，不会在这一列
    int row = 0;
    int column = array[0].length - 1;

    while (row < array.length - 1 && column >= 0) {
      //
      if (num > array[row][column]) {
        row = row + 1;
      } else if (num < array[row][column]) {
        column = column - 1;
      } else {
        flag = true;
        break;
      }
    }

    if (flag) {
      System.out.println("找到了数字" + num);
    } else {
      System.out.println("未找到数字" + num);
    }

  }


  /**
   * 打印二维数组
   */
  public void printArray(int[][] array) {
    for (int i = 0; i < array.length; i++) {
      System.out.print("{");
      for (int j = 0; j < array[i].length; j++) {
        System.out.print(array[i][j] + " ");
      }
      System.out.println("}");
    }
  }


  public static void main(String args[]) {
    FindInTwoArray findInTwoArray = new FindInTwoArray();
    int[][] array = new int[][]{{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
//        findInTwoArray.printArray(array);
    findInTwoArray.findNum2(array, 7);
  }

}

